// 二叉树的前序遍历
package Leetcode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

// 迭代解法
// 我们维护一个栈，当栈顶元素出栈时，我们访问它，由于先序遍历的顺序为根左右，
// 于是我们在让根节点出栈的同时，先后入栈根结点的右子树和左子树
class Solution_144_1 {
    public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        if (root == null)
            return list;
        stack.push(root);
        // 根结点出栈的同时先入栈右子树再入栈左子树
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            if (node.right != null)
                stack.push(node.right);
            if (node.left != null)
                stack.push(node.left);
        }
        return list;
    }
}

class Solution_144_2 {
    List<Integer> list = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null)
            return null;
        preorder(root);
        return list;
    }

    void preorder(TreeNode root) {
        if (root == null)
            return;
        list.add(root.val);
        preorder(root.left);
        preorder(root.right);
    }
}

// Mirrors解法，以某个根结点开始，找到它左子树的最右侧节点之后与这个根结点进行连接
class Solution_144_3 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode currentRoot = root; // 当前开始遍历的结点
        TreeNode cur = null; // 记录当前结点的左子树

        while (currentRoot != null) {
            cur = currentRoot.left;
            // 如果当前结点有左子树
            if (cur != null) {
                // 左子树的右节点不为空且还没有与根结点建立连接
                while (cur.right != null && cur.right != currentRoot)
                    cur = cur.right;
                // 此时要么cur.right==null,要么cur.right==currentRoot
                // 这个时候如果最右侧这个节点的右指针没有指向根结点，创建连接然后往下一个左子树的根结点进行连接操作。
                if (cur.right == null) {
                    cur.right = currentRoot;
                    list.add(currentRoot.val);
                    currentRoot = currentRoot.left;
                    continue;
                }
                // 当左子树的最右侧节点有指向根结点，此时说明我们已经回到了根结点并重复了之前的操作，
                // 同时在回到根结点的时候我们应该已经处理完左子树的最右侧节点了，把路断开。
                else {
                    cur.right = null;
                }
            } // if
            else {
                list.add(currentRoot.val);
            }
            // 不是回到上一个根结点，而是到当前root的右子树
            currentRoot = currentRoot.right;
        } // while

        return list;
    }
}